package com.xgh.offer;

/**
 * @ClassName Offerr53_2
 * @Description
 * @Author xinggh
 * @Date 2020/7/3 9:24
 * @Version 1.0
 **/
public class Offerr53_2 {
    /**
     * 剑指 Offer 53 - II. 0～n-1中缺失的数字
     * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
     * <p>
     * <p>
     * <p>
     * 示例 1:
     * <p>
     * 输入: [0,1,3]
     * 输出: 2
     * 示例 2:
     * <p>
     * 输入: [0,1,2,3,4,5,6,7,9]
     * 输出: 8
     */

    public static int missingNumber(int[] nums) {

        int start = 0;
        int end = nums.length;


        while (start < end) {
            int mid = (start + end) / 2;
            if (nums[mid] == mid) {
                start++;
            } else {
                end--;
            }
        }

        return start;
    }

    public static void main(String[] args) {
        int nums[] = {0,1,2,3,4,5,6,7,9};
        System.out.println(missingNumber(nums));
    }
}
